package q204_countPrimes;

import java.util.Arrays;

public class Solution_2 {
    /*
    埃及筛：
    考虑到：如果x为质数，那么大于x的2x 3x都不是质数
    我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。
    从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，
    这样在运行结束的时候我们即能知道质数的个数。
     */
    public int countPrimes(int n) {
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                // 注意要用long
                if ((long) i * i < n) {
                    // 注意 这里的标法是直接从 i * i开始 然后每次 +i 进行标记
                    // 而不是从2i 3i 。。。 反复标记
                    // 因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }

}
